#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> findSubstring(string s, vector<string> &words)
    {
        vector<int> ans;
        if (words.empty())
            return ans;

        int wordLen = words[0].size();
        int totalWords = words.size();
        int windowLen = wordLen * totalWords;
        if (s.size() < windowLen)
            return ans;

        // 统计目标单词的频率
        unordered_map<string, int> targetFreq;
        for (const string &word : words)
        {
            targetFreq[word]++;
        }

        // 滑动窗口检查所有可能的起始位置
        for (int i = 0; i <= s.size() - windowLen; i++)
        {
            unordered_map<string, int> windowFreq;
            int j = 0;
            // 提取窗口内的单词并统计频率
            while (j < totalWords)
            {
                string word = s.substr(i + j * wordLen, wordLen);
                windowFreq[word]++;
                j++;
            }
            // 比较窗口频率和目标频率
            if (windowFreq == targetFreq)
            {
                ans.push_back(i);
            }
        }
        return ans;
    }
};